/*
 * slide window, 判断是否包含子串的排列
 * https://leetcode-cn.com/problems/permutation-in-string/submissions/
 */

typedef struct {
    int ch;
    int cnt;
    UT_hash_handle hh;
} ut_hash_t;

ut_hash_t *sub_map = NULL;
ut_hash_t *window = NULL;

void add_sub_int(int ch)
{
    ut_hash_t *s = NULL;
    HASH_FIND_INT(sub_map, &ch, s);
    if (s == NULL) {
        s = (ut_hash_t*)malloc(sizeof(*s));
        s->ch = ch;
        s->cnt = 0;
        HASH_ADD_INT(sub_map, ch, s);
    }
    s->cnt++;
}
ut_hash_t *find_sub_int(int ch)
{
    ut_hash_t *s = NULL;

    HASH_FIND_INT(sub_map, &ch, s);

    return s;
}
ut_hash_t *add_window_int(int ch)
{
    ut_hash_t *s = NULL;
    HASH_FIND_INT(window, &ch, s);
    if (s == NULL) {
        s = (ut_hash_t *)malloc(sizeof(*s));
        s->ch = ch;
        s->cnt = 0;
        HASH_ADD_INT(window, ch, s);
    }
    s->cnt++;
    return s;
}
ut_hash_t *find_window_int(int ch)
{
    ut_hash_t *s = NULL;

    HASH_FIND_INT(window, &ch, s);

    return s;
}

bool checkInclusion(char * s1, char * s2){
    sub_map = NULL;
    window = NULL;

    int left = 0, right = 0;
    for (int i = 0; i < strlen(s1); ++i) {
        add_sub_int(s1[i]);
    }

    int len = INT_MAX;
    int valid = 0;
    while (right < strlen(s2)) {
        char a = s2[right];
        right++;
        ut_hash_t *sub = find_sub_int(a);
        if (sub != NULL && sub->cnt > 0) {
            ut_hash_t *win = add_window_int(a);
            if (win->cnt == sub->cnt) {
                valid++;
            }
        }

        while (right-left >= strlen(s1)) {
            if (valid == HASH_COUNT(sub_map)) return true;
            char b = s2[left];
            left++;
            ut_hash_t *win = find_window_int(b);
            if (win != NULL) {
                ut_hash_t *sb = find_sub_int(b);
                if (win->cnt == sb->cnt) {
                    valid--;
                }
                win->cnt--;
            }
        }
    }

    return false;
}
